package 回溯;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 活字印刷1079.java
 * @createTime 2023年02月16日 19:49:00
 */
public class 活字印刷1079 {
	public int numTilePossibilities(String tiles) {
		char[] chars = tiles.toCharArray();
		Arrays.sort(chars);
		int[] res=new int[1];
		backTrace(chars, 0, res, new boolean[chars.length]);
		return res[0];
	}

	public void backTrace(char[] tiles, int index, int[] temp, boolean[] used) {
		if (tiles.length == index) {
			return;
		}
		for (int i = 0; i < tiles.length; i++) {
			if (used[i]) {
				continue;
			}
			//
			if (i - 1 >= 0 && tiles[i] == tiles[i - 1] && !used[i - 1]){
				continue;
			}
			used[i] = true;
			temp[0]++;
			backTrace(tiles, index + 1, temp, used);
			used[i] = false;
		}
	}
}
